package zhengqc.graph.algorithm;

import zhengqc.graph.data_structure.Graph;

import java.util.ArrayList;

/* Connected Component
*  连通分量, 适用于无向图 */
public class ConnectedComponent {
    private Graph graph;
    private int[] visited;
    private int count = 0;

    public ConnectedComponent(Graph graph) {
        if (graph.isDirected()) {
            throw new IllegalArgumentException("CC doesn't work in Directed-Graph");
        }
        this.graph = graph;
        this.visited = new int[graph.getV()];
        for (int i = 0; i < visited.length; ++i) {
            visited[i] = -1;
        }
        for (int v = 0; v < graph.getV(); ++v) {
            if (visited[v] == -1) {
                dfs(v, count);
                this.count ++;
            }
        }
    }
    private void dfs(int v, int cc_id) {
        this.visited[v] = cc_id;
        for (int w: graph.getAdjacency(v)) {
            if (visited[w] == -1) {
                dfs(w, cc_id);
            }
        }
    }
    public int getCount() {
        return this.count;
    }
    public boolean isConnected(int v, int w) {
        graph.validateVertex(v);
        graph.validateVertex(w);
        return visited[v] == visited[w];
    }
    public ArrayList<Integer>[] getComponents() {
        ArrayList<Integer>[] components = new ArrayList[count];
        for (int i = 0; i < count; ++i) {
            components[i] = new ArrayList<>();
        }
        for (int v = 0; v < graph.getV(); ++v) {
            components[visited[v]].add(v);
        }
        return components;
    }
}
